package org.sang.test;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Solution {

    public static void main(String[] args) {
        int[] numArray = new int[]{9,10,9,-7,-3,8,2,-6};
        int size = 5;
        ArrayList<Integer> list = maxInWindows(numArray, size);
        System.out.println(list);
    }
    /**
     * 滑动窗口
     * @param num
     * @param size
     * @return
     */
    public static ArrayList<Integer> maxInWindows(int[] num, int size) {

        ArrayList<Integer> res = new ArrayList<Integer>();
        //窗口大于数组长度的时候，返回空
        if(size <= num.length && size != 0){
            //双向队列
            ArrayDeque <Integer> dq = new ArrayDeque<Integer>();
            //先遍历一个窗口
            for(int i = 0; i < size; i++){
                //去掉比自己先进队列的小于自己的值
                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
                    dq.pollLast();
                dq.add(i);
            }
            //遍历后续数组元素
            for(int i = size; i < num.length; i++){
                //取窗口内的最大值
                res.add(num[dq.peekFirst()]);
                while(!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
                    //弹出窗口移走后的值
                    dq.pollFirst();
                //加入新的值前，去掉比自己先进队列的小于自己的值
                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
                    dq.pollLast();
                dq.add(i);
            }
            res.add(num[dq.pollFirst()]);
        }
        return res;
    }
}
